package com.gitee.wsl.collections.queue

import com.gitee.wsl.ext.base.Arrays.newArray
import com.gitee.wsl.ext.array.heapifyDown
import com.gitee.wsl.ext.array.heapifyUp

// https://github.com/badoo/Reaktive/blob/master/reaktive/src/commonMain/kotlin/com/badoo/reaktive/utils/queue/PriorityQueue.kt
class ArrayQueue<T>(
    private val comparator: Comparator<in T>?=null
): Queue<T> {

    private var array: Array<T?>? = null

    private var _size: Int = 0

    override fun peekOrNull(): T? = array?.takeUnless { isEmpty() }?.get(0)

    override fun add(element: T): Boolean {
        if (element == null)
            throw NullPointerException()
        var arr: Array<T?>? = array
        if (arr == null) {
            arr = newArray()
        } else if (_size == arr.size) {
            arr = arr.copyOf(_size * 2)
        }
        array = arr

        val lastIndex = _size++
        arr[lastIndex] = element
        @Suppress("UNCHECKED_CAST")
        comparator?.let {
            (arr as Array<T>).heapifyUp(lastIndex, comparator)
        }
        return true
    }

    override fun pollOrNull(): T? {
        val arr = array
        if ((arr == null) || isEmpty()) {
            return null
        }

        val lastIndex = --_size
        val item = arr[0]
        arr[0] = arr[lastIndex]
        arr[lastIndex] = null
        @Suppress("UNCHECKED_CAST")
        comparator?.let {
            (arr as Array<T>).heapifyDown(0, _size, comparator)
        }
        return item
    }

    override val size: Int
        get() = _size

    override fun isEmpty(): Boolean = _size == 0

    override fun clear() {
        array = null
        _size = 0
    }

    override fun remove(element: T): Boolean {
        val index = indexOf(element)
        if(index >= 0){
            remove(index)
            return true
        }
        return false
    }

    fun remove(index:Int){
        array?.let {
            if(index<_size) {
                it.copyInto(it, index + 1)
                _size--
            }
        }
    }

    override fun containsAll(elements: Collection<T>): Boolean {
        return elements.all { array?.contains(it) ?: false }
    }

    override fun contains(element: T): Boolean {
        return array?.contains(element) ?: false
    }

    /**
     * The doc is derived from Java PriorityQueue.
     *
     * Returns an iterator over the elements in this queue. The
     * iterator does not return the elements in any particular order.
     *
     * @return an iterator over the elements in this queue
     */
    override fun iterator(): MutableIterator<T> =
        object : MutableIterator<T> {

            private var index = 0

            override fun hasNext(): Boolean = index < _size

            @Suppress("UNCHECKED_CAST")
            override fun next(): T {
                val arr = array?.takeIf { index < _size } ?: throw NoSuchElementException()

                return arr[index++] as T
            }

            override fun remove() {
                remove(index)
            }
        }


}